package leetcode.code139;

import java.util.List;

/**
 * 改失败了
 * @author CaoYu
 * @date 2021年9月14日
 * @description
 */
public class Solution1 extends Solution139 {

	private class DicNode {
		public DicNode(char c) {
			this.c = c;
		}

		public char c;
		public DicNode[] next = new DicNode[128];
		public boolean isEnd;

		public DicNode hasChar(char c) {
			return next[c];
		}

		public DicNode setChar(char c) {
			if (next[c] == null) {
				DicNode dn = new DicNode(c);
				next[c] = dn;
				return dn;
			}
			return next[c];
		}

	}

	private DicNode buildDicTree(List<String> wordDict) {
		DicNode head = new DicNode('*');
		for (String wd : wordDict) {
			DicNode dn = null;
			for (char c : wd.toCharArray()) {
				if (dn == null) {
					dn = head.setChar(c);
				} else {
					dn = dn.setChar(c);
				}
			}
			dn.isEnd = true;
		}
		return head;
	}

	@Override
	public boolean wordBreak(String s, List<String> wordDict) {
		DicNode head = this.buildDicTree(wordDict);
		char[] chars = s.toCharArray();
		boolean[] dp = new boolean[chars.length + 1];
		dp[0] = true;
		for (int i = 1; i < chars.length; i++) {
			for (int j = 0; j <= i; j++) {
				if (dp[j] && this.wordBreak(s, wordDict))
					dp[i] = true;
			}
		}
		return dp[chars.length];
	}

	public DicNode isPartOfDicNode(DicNode head, char[] chars, int start, int end) {
		DicNode dn1 = head;
		DicNode dn2 = null;
		for (int i = start; i < end; i++) {
			dn2 = dn1.hasChar(chars[i]);
			if (dn2 == null && i != end - 1) {
				return null;
			} else if (dn2 == null && i == end - 1) {
				return dn1;
			} else if (dn2 != null && i != end - 1) {
				dn1 = dn2;
			} else {
				return dn1;
			}
		}
		return dn1;
	}

	public boolean isPartOf(DicNode head, char[] chars, int start, int end) {
		DicNode dn1 = head;
		DicNode dn2 = null;
		for (int i = start; i < end; i++) {
			dn2 = dn1.hasChar(chars[i]);
			if (dn2 == null && i != end - 1) {
				return false;
			} else if (dn2 == null && i == end - 1) {
				return dn1.isEnd;
			} else if (dn2 != null && i != end - 1) {
				dn1 = dn2;
			} else {
				return dn1.isEnd;
			}

		}
		return false;
	}

	public static void main(String[] args) {
		System.out.println("这个字典树改失败了，需要重新学习");
		Solution1 so = new Solution1();
		so.debug1("leetsscode");
		so.debug2();
		so.debug3();
		so.debug4();
//		System.out.println((int) 'a');
//		System.out.println((int) 'z');
	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

}
